package finance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import org.apache.commons.math.complex.Complex;
import org.apache.commons.math.transform.FastFourierTransformer;

public class FFT {
    public int shift(int i, int l) {
        int shifted = 0;

        if (i < l / 2) {
            shifted = i + l / 2;
        } else {
            shifted = i - l / 2;
        }

        return shifted;
    }
    
    public List<Long> fft(double[] doubles) {
        FastFourierTransformer transformer = new FastFourierTransformer();
        Complex[] transformed = transformer.transform(doubles);
        double[] shiftedAbs = new double[transformed.length];
        double[] f = new double[transformed.length];
        TreeMap<Double, Double> map = new TreeMap<Double, Double>();

        for (int i = 0; i < transformed.length; i++) {
            shiftedAbs[shift(i, transformed.length)] = transformed[i].abs();
            f[i] = -0.5 + i / (double) doubles.length;
        }

        for (int i = 0; i < shiftedAbs.length; i++) {
            map.put(shiftedAbs[i], f[i]);
        }

        List<Long> periods = new ArrayList<Long> ();
        for (Map.Entry<Double, Double> entry : map.entrySet()) {
            Double key = entry.getKey();
            Double value = entry.getValue();
            
            if(value > 0) {
                periods.add( Math.round(1/value) );
            }
        }
        
        return periods;
    }
}
